package algorithmExample.linkedlist;

import java.util.HashSet;
import java.util.Set;

/**
 * @Author: zhangrongqing
 * @Date: 2019/11/29 10:06
 */
//题目:https://leetcode-cn.com/problems/linked-list-cycle-ii/


public class LinkedListCycle {
    //运用额外空间记录
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> listNodes = new HashSet<>();
        while (head != null) {
            if (listNodes.contains(head)) {
                return head;
            }
            listNodes.add(head);
            head = head.next;
        }
        return null;
    }

    //快慢指针，只要有环的话，一定会相遇
    public ListNode detectCycle2(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode fast = head, slow = head;
        while (slow != null && fast != null) {
            slow = slow.next;
            fast = fast.next;   //while判断过了null
            if (fast == null) {
                return null;
            }
            fast = fast.next; //再判断一次保证不是null
            if (fast == slow) {            //有相等，证明有环
                System.out.println(fast.val);
                return findCycleListNode(fast, head);
            }
        }
        return null;
    }

    private ListNode findCycleListNode(ListNode fast, ListNode head) {  //有环开始以后,每次走一格就能在环出相遇。
        while (true) {
            if (head == fast) {
                return head;
            }
            head = head.next;
            fast = fast.next;
        }
    }
}
